package cc.wsyw126.java.nowcoder.sword_offer;

/**
 * Created by dp on 2017/4/19.
 * 给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
 */
public class KthNode {
    private int count = 0;

    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot != null) {
            TreeNode treeNode = KthNode(pRoot.left, k);
            if (treeNode != null) return treeNode;
            if (++count == k) return pRoot;
            treeNode = KthNode(pRoot.right, k);
            if (treeNode != null) return treeNode;
        }
        return null;
    }

    public static void main(String[] args) {
        //8,6,10,5,7,9,11
        TreeNode treeNode8 = new TreeNode(8);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode10 = new TreeNode(10);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode11 = new TreeNode(11);

        treeNode8.left = treeNode6;
        treeNode8.right = treeNode10;
        treeNode6.left = treeNode5;
        treeNode6.right = treeNode7;
        treeNode10.left = treeNode9;
        treeNode10.right = treeNode11;

        KthNode kthNode = new KthNode();
        TreeNode treeNode = kthNode.KthNode(treeNode8, 2);
        System.out.println("treeNode.val = " + treeNode.val);
    }
}
